// 生成函数的应用
// n 块砖排成一行，每块砖可以被涂成红、蓝、绿、黄
// 四种颜色，求最后涂成红、绿的砖的数目均为偶数的
// 方案数。
// 注意：1 <= n <= 10^9，结果对 10007 取模。
// 测试链接 ：http://poj.org/problem?id=3734
// 相关帖子 ：https://www.cnblogs.com/dx123/p/16899614.html
// 相关帖子 ：https://oi-wiki.org/math/poly/ogf/#%E5%BA%94%E7%94%A8
// 提交以下的code，可以直接通过

#include <cstdio>

using namespace std;

const int P = 10007;

int quickPow(int a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return ans;
}

int main()
{
    int t, n, ans;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        ans = (quickPow(4, n -1) + quickPow(2, n - 1)) % P;
        printf("%d\n", ans);
    }

    return 0;
}